package divideTwoIntegers;



public class Solution {
    public int divide(int dividend, int divsor) {
        int sign=1;
        long l,r;
        if (dividend == 0 || divsor == 0) return 0;  
        long longDividend=dividend;
        long longDivsor=divsor;
        if (longDividend<0) { sign=-sign; longDividend=-longDividend;}
        if (longDivsor<0) { sign=-sign; longDivsor=-longDivsor;}
        if (longDivsor>longDividend) return 0;
        l=1; r=longDividend;
        while (l+1<r){
        	long LongMid=(l + r) >>1;
        	int mid=(int) LongMid;
            long now=fastM(mid,longDivsor);
        	if (now==longDividend) return mid*sign;
        	if (now>longDividend) r=mid;
        	if (now<longDividend) l=mid;
        }
        if (fastM(r,longDivsor)==longDividend) 
        	if ((r*sign>=Integer.MIN_VALUE) && (r*sign<=Integer.MAX_VALUE)) return (int) (r*sign);
        	else return Integer.MAX_VALUE;
        else return (int) (l*sign);
        
    }
    public long fastM(long times,long base){
    	boolean bo;
    	long count=1;
    	long now=base;
    	if ((times & 1)==1) {bo=true; times=times-1;}
    	else bo=false;
    	while (count<times){
    		if ((count << 1)<=times) {
    			now=now << 1;
    			count=count << 1;
    		}
    		else{
    			long tempNow= now;
    			long tempCount= count;
    			long need=(times-count);
    			while (need>0){
    				if (tempCount<=need){
    					need=need-tempCount;
    					now=now+tempNow;
    				}
    				else{
    				tempCount=tempCount >> 1;
    			    tempNow=tempNow >> 1;
    				}
    			}
    			break;
    		}
    	}
    	if ((bo)&&(times!=0)) now=now+base;
    	return  now;
    }
    public static void main(String args[]){
    	Solution so=new Solution();
    	System.out.println(so.divide(-2147483648,-2147483648));
    }
}

/* 29. Divide Two Integers
 * 细节比算法重要系列。。
 * 细节：1.jvm蜜汁爆int设定。。
 *      2.位数算跳溢出设定
 * 算法：二分ans+位运算累乘+（理论上存在的记忆化优化）
 * 果然低AC率的题目都有毒TAT
 * 
 */

